Greg Detre
14:30 Wednesday, September 25, 2002
see lecture
notes � uninformed search: breadth-first, uniform-cost, depth-first,
depth-limited, iterative-deepening, bi-directional
measure:
time � total number of elements
space � the largest the queue will ever get
use a
heuristic to choose a node to expand
evaluation function, f(n)
a heuristic should be:
cheap to compute
provide useful information to guide search
= �useful but not necessarily correct�
with the right heuristic, we could do best-first search
order the nodes in the queue by the evaluation-function
greedy best-first search
let�s say we had the distance as-the-crow-flies from each Romanian town to Bucharest
you know that the distance to Bucharest will be smaller (or equal to) the distance of the route (since you won�t be travelling as the crow flies)
if you know the distance from where you are to each nearby town, you could factor that into your heuristic, so that you�re minimising the hop distance each time, as well as maximising the progress you make towards Bucharest � i.e. add the cost incurred so far
this is the A* search
do you want to subtract the distance of the most recent hop, or the total distance travelled so far from Arad?
could you not do iterative-deepening two steps at a time (because you know all of the routes are quite convoluted)???
in the case of the 8-puzzle, you could use a greedy search
with the heuristic of counting the number of tiles out of place (easy to compute and yet useful), you could save some time
and again, the heuristic provides a lower bound, e.g. if it says there are 4 tiles out of place, then you�ve got to make at least 4 moves to get to the goal
this is closer to depth-first search, has similar time complexity, higher space complexity, and can get stuck fruitlessly wandering
A* search
f(n) = g(n) + h(n)
takes into account distance to goal, as well as cost incurred
doesn�t check ancestors, allow them to be added as open nodes, but they don�t get explored because they�re clearly crap
however, it could get caught in a loop in certain cases, if places are very close together
you know that you don�t have to check from Oradea, having found somewhere else, because the f(n) from Oradea is already above the goal distance we�ve found
i.e. the heuristic value that we�ve used to calculate the f(n) for Oradea is a lower bound, i.e. a best-case scenario � if that best-case scenario isn�t better than the route we�ve already found, then don�t bother check past Oradea
an admissible heuristic is optimistic
it never overestimates the future cost in a minimisation problem, and never underestimates the future value in maximisation problem
A* search with an admissible heuristic is complete & optimal
proof of optimality � see lecture notes
consistent (aka monotonic) heuristic
� ???
f(n) never decreases along a path
consistency implies admissibility, though not necesssarily the other way round
running an A* search h(n) = 0 is a breadth-first/uniform-cost search (is still complete and optimal)
what�s the worst case?
iterative-deepening A* - helps with space complexity
do A* up to a cut-off in f
goal state for 8-puzzle
h1�� number of tiles out of place
h2�� total manhattan distance (= straight line distance???)
need to be able to move the piece, but leave the other pieces where they are
this amounts to the relaxed problem where a tile can just move from A to B (not just if adjacent or B is blank)
dominating heuristics (e.g. h2) always dominates other admissible heuristics, remains admissible and provdes more search info
there�s a trade-off between a heuristic which saves search time and spending extra time computing more complex heuristics
Absolver
can generate heuristics automatically from problem definitions
����� able to solve Rubik�s cube by relaxing the problem in an interesting way
learning methods
pick features, use machine learning based on example to determine the contributions of various features
how to solve bigger 8-puzzles
combine heuristics
solve a sub-problem
pattern database
all possible sub-problem configurations, build a look-up table for these off-line
disjoint pattern database
add together two costs
24-puzzle is still difficult, but a millino times faster than the Manhattan heuristic
admissible vs consistent heuristics???
what�s a relaxed problem???
relaxed versions of the problem are easier to solve (require less computation), and provide us with admissible numbers
what�s the difference between a relaxed and a sub-problem???